Web search is the gateway to the Internet for billions of users daily. When a user issues a query to a search engine, two separate searches are evaluated: the search over the corpus of pre-crawled Web pages is called Web search; the ads that are displayed at the top and the side of the Web search results are retrieved by sponsored search. Sponsored search provides revenue for the search engine and brings users to numerous advertiser sites.
Web search and sponsored search differ in a few key aspects. Sponsored search is evaluated over a set of ads that promote products and services. As it is customary in the advertising world, the textual content visible to the user (e.g., ad creative), is generated by an advertiser to maximize a response of a target audience. In Web search, on the other hand, the snippet shown on the search result page is generated automatically by the summarization mechanism of the search engine. Another important difference is in the way the ads and the Web results are selected. While the Web pages are selected based on their content, the ad selection depends heavily on the use of an ad bid phrase, which is a query that the advertiser has specified as suitable for the ad. In the early days of the sponsored search marketplace, this mechanism allowed for simple ad selection where the whole burden and control is shifted to the advertiser. However, with the development of the sponsored search market, it has quickly become apparent that the advertisers most likely cannot find all the queries that could be relevant to their ads.
To alleviate this problem the search engines allow for advanced match where an ad can be selected even if the bid phrase does not match the query. The advanced match problem corresponds closer to the Web search problem. Recent advanced match approaches use search techniques for ad selection by evaluating the query over a corpus of documents that are created from the ads. One of the key difficulties in this ad retrieval approach is that the ads are much shorter than documents in most other search applications.